package com.company.algo.tree;

import com.company.algo.pojo.TreeNode;

/**
 * 力扣第 105 题
 * 通过前序和中序遍历结果构造二叉树
 */
public class BuildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if (len < 1) return null;
        return buildTree(preorder, 0, len - 1, inorder, 0, len - 1);
    }

    public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
                              int[] inorder, int inStart, int inEnd) {
        //base case
        if (preStart > preEnd) return null;

        //确定根节点的值
        int rootVal = preorder[preStart];
        int rootIdx = -1;
        //确定inorder中根节点的下标
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIdx = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        int leftLen = rootIdx - inStart;
        //构造左子树
        root.left = buildTree(preorder, preStart + 1, preStart + leftLen,
                inorder, inStart, rootIdx - 1);
        //构造右子树
        root.right = buildTree(preorder, preStart + leftLen + 1, preEnd,
                inorder, rootIdx + 1, inEnd);
        return root;
    }
}
